package com.lry.basic.algorithm.graph;

import java.util.ArrayList;

public class FindBridges {

    private UndirectedGraph G;
    private boolean[] visited;
    private int ord[];
    private int low[];
    private int cnt;

    private ArrayList<Edge> res;

    public FindBridges(UndirectedGraph G){
        this.G = G;
        visited = new boolean[G.vertexNum()];

        res = new ArrayList<>();
        ord = new int[G.vertexNum()];
        low = new int[G.vertexNum()];
        cnt = 0;

        for(int v = 0; v < G.vertexNum(); v ++)
            if(!visited[v])
                dfs(v, v);
    }

    private void dfs(int v, int parent) {
       visited[v] = true;
       ord[v] = cnt;
       low[v] = ord[v];
       cnt++;

       for(int w:G.adj(v)){
            if(!visited[w]){
                dfs(w,v);
                //回退的时候
                low[v] = Math.min(low[v], low[w]);
                if(low[w]>ord[v]){
                    res.add(new Edge(v, w));
                }
            }else if(w!=parent){
                low[v] = Math.min(low[v], low[w]);
            }
       }
    }

    public ArrayList<Edge> result(){
        return res;
    }


    public static void main(String[] args){

        UndirectedGraph g = new UndirectedGraph("graph.txt");
        FindBridges fb = new FindBridges(g);
        System.out.println("Bridges in g : " + fb.result());

    }


    class Edge {
        private int v, w;
        public Edge(int v, int w){
            this.v = v;
            this.w = w;
        }
        @Override
        public String toString(){
            return String.format("%d-%d", v, w);
        }
    }
}
